public class test {
    //leetcode 63.不同路径Ⅱ
    class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            // 1. 创建dp[][]表
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[][] dp = new int[m+1][n+1];
            // 2. 初始化
            dp[0][1] = 1;
            // 3. 填表
            for(int i = 1;i <= m;i++){
                for(int j = 1;j <= n;j++){
                    if(obstacleGrid[i-1][j-1] == 1) {
                        continue;
                    }
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
            // 4. 返回值
            return dp[m][n];
        }
    }
    //leetcode LCR 166.珠宝的最高价值
    class Solution {
        public int jewelleryValue(int[][] frame) {
            // 1. 创建dp[][]表
            int m = frame.length;
            int n = frame[0].length;
            int[][] dp = new int[m+1][n+1];
            // 2. 初始化

            // 3. 填表
            // (dp[i][j]表示从起点到该位置能拿到的最高价值)
            for(int i = 1;i <= m;i++){
                for(int j = 1;j <= n;j++){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + frame[i-1][j-1];
                }
            }
            // 4. 返回值
            return dp[m][n];
        }
    }
    //leetcode 931.下降路径最小和
    class Solution {
        // 法1. 直接创建dp表,无辅助空间,手动处理越界
        public int minFallingPathSum1(int[][] matrix) {
            // 1. 创建dp[][]表
            int m = matrix.length;
            int n = matrix[0].length;
            int[][] dp = new int[m][n];
            // 2. 初始化
            for(int i = 0;i < n;i++){
                dp[0][i] = matrix[0][i];
            }
            // 3. 填表
            // dp[i][j]代表开始到此位置的最小和
            for(int i = 1;i < m;i++){
                for(int j = 0;j < n;j++){
                    int left = j > 0 ? dp[i-1][j-1] : Integer.MAX_VALUE;
                    int mid = dp[i-1][j];
                    int right = j < n - 1 ? dp[i-1][j+1] : Integer.MAX_VALUE;
                    dp[i][j] = Math.min(Math.min(left,mid),Math.min(mid,right)) + matrix[i][j];
                }
            }
            // 4. 返回值
            int min = Integer.MAX_VALUE;
            for(int i = 0;i < n;i++){
                min = Math.min(min,dp[m-1][i]);
            }
            return min;
        }
        // 法2. 创建多一圈的dp表,防止越界
        public int minFallingPathSum(int[][] matrix) {
            // 1. 创建dp[][]表
            int m = matrix.length;
            int n = matrix[0].length;
            //(多一圈,左右各加一列)
            int[][] dp = new int[m+1][n+2];
            // 2. 初始化
            for(int i = 1;i < m + 1;i++){
                dp[i][0] = Integer.MAX_VALUE;
                dp[i][n+1] = Integer.MAX_VALUE;
            }
            // 3. 填表
            // dp[i][j]代表开始到此位置的最小和
            for(int i = 1;i <= m;i++){
                for(int j = 1;j <= n;j++){
                    dp[i][j] = Math.min(Math.min(dp[i-1][j+1],dp[i-1][j]),Math.min(dp[i-1][j],dp[i-1][j-1])) + matrix[i-1][j-1];
                }
            }
            // 4. 返回值
            int min = Integer.MAX_VALUE;
            for(int i = 1;i <= n;i++){
                min = Math.min(dp[m][i],min);
            }
            return min;
        }
    }
}